#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long t,n,m,f[N*2+5],top,ans,f1[N*2+1],bq,now,l,r,ans1,ans2,ans3;
struct node2{
	int l,r;
	bool friend operator<(node2 i,node2 j)
	{
		if(i.l==j.l) return i.r<j.r;
		return i.l<j.l;
	}
};
map<node2,int>p;
struct node{
	int l,r,z;
}a[N];
struct node1{
	int l,r,ll,rr;
	long long z;
}b[N];
bool cmp(node i,node j)
{
	if(i.r-i.l==j.r-j.l) return i.l<j.l;
	return i.r-i.l<j.r-j.l;
}
bool cmp1(node i,node j)
{
	return i.z<j.z;
}
int find(int i)
{
	if(f[i]==i) return i;
	return f[i]=find(f[i]);
}
int find1(int i)
{
	if(f1[i]==i) return i;
	return f1[i]=find1(f1[i]);
}
int main()
{
	freopen("up.in","r",stdin);
	freopen("up.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		top=0;
		for(int i=1;i<=m;++i)
			cin>>a[i].l>>a[i].r>>a[i].z,p[(node2){a[i].l,a[i].r}]=p[(node2){a[i].r,a[i].l}]=a[i].z+1;
		sort(a+1,a+m+1,cmp);
		for(int i=1;i<=m;++i)
		{
			if(a[i].r-a[i].l!=1) break;
			++top,b[top].l=b[top-1].r+1,b[top].r=a[i].l,b[top].z=b[top].r-b[top].l,f1[top]=top,b[top].ll=b[top].l,b[top].rr=top;
		}
		if(b[top].r!=n)
		++top,b[top].l=b[top-1].r+1,b[top].r=n,b[top].z=b[top].r-b[top].l,f1[top]=top,b[top].ll=b[top].l,b[top].rr=top;
		ans=top-1;
		now=1;
		sort(a+1,a+m+1,cmp1);
		for(;now<=m;++now)
		{
			if(a[now].z>=1) break;
			if(!f[a[now].l])
				f[a[now].l]=a[now].l;
			if(!f[a[now].r])
				f[a[now].r]=a[now].r;
			l=1,r=top;
			while(l<=r)
			{
				int mid=(l+r)/2;
				if(a[now].l<=b[mid].r)
					r=mid-1,ans1=mid;
				else
					l=mid+1;
			}
			l=1,r=top;
			while(l<=r)
			{
				int mid=(l+r)/2;
				if(a[now].r<=b[mid].r)
					r=mid-1,ans2=mid;
				else
					l=mid+1;
			}
			if(ans1!=ans2&&find1(ans1)!=find1(ans2))
				f1[f1[ans1]]=f1[ans2],--ans,f[find(a[now].l)]=find(a[now].r);
			else{
				if(find(a[now].l)!=find(a[now].r))
				{
					if(ans1==ans2)
						b[ans1].z-=1;
					f[f[a[now].l]]=f[a[now].r];
				}
			}
		 } 
		for(;now<=m;++now)
		{
			if(a[now].z>=2||ans<=0) break;
			if(!f[a[now].l])
				f[a[now].l]=a[now].l;
			if(!f[a[now].r])
				f[a[now].r]=a[now].r;
			l=1,r=top;
			while(l<=r)
			{
				int mid=(l+r)/2;
				if(a[now].l<=b[mid].r)
					r=mid-1,ans1=mid;
				else
					l=mid+1;
			}
			l=1,r=top;
			while(l<=r)
			{
				int mid=(l+r)/2;
				if(a[now].r<=b[mid].r)
					r=mid-1,ans2=mid;
				else
					l=mid+1;
			}
			if(find1(ans1)!=find1(ans2))
				f1[f1[ans1]]=f1[ans2],--ans,++ans3,f[find(a[now].l)]=find(a[now].r);
		 } 
		bq=1;
		while(ans>0)
		{
			if(n-bq<=0)
				bq=a[now].z;
			else
				++bq;
			for(int i=1;i<=top;++i)
			{
				if(ans<=0) break;
				for(int j=max(0ll,b[i].l-bq);j<min(1ll*b[i].ll,b[i].r-bq+1);++j)
				{
				if(ans<=0) break;
//				cout<<p[(node2){j+bq,j}]<<" ";
				if(p[(node2){j+bq,j}]!=0) continue;
				l=1,r=top;
				while(l<=r)
				{
					int mid=(l+r)/2;
					if(j<=b[mid].r)
						r=mid-1,ans1=mid;
					else
						l=mid+1;
				}
				if(find1(ans1)!=find1(i))
				{
					ans3+=bq;
					f1[f1[ans1]]=f1[i];
					--ans;
					if(b[i].ll-1==b[ans1].r)
						b[i].ll=b[ans1].ll,b[ans1].rr=b[i].rr;
				}
				}
				i=b[i].rr;
			}
			for(;now<=m;++now)
			{
				if(a[now].z>bq||ans<=0) break;
//				cout<<ans<<" ";
				if(!f[a[now].l])
					f[a[now].l]=a[now].l;
				if(!f[a[now].r])
					f[a[now].r]=a[now].r;
				l=1,r=top;
				while(l<=r)
				{
					int mid=(l+r)/2;
					if(a[now].l<=b[mid].r)
						r=mid-1,ans1=mid;
					else
						l=mid+1;
				}
				l=1,r=top;
				while(l<=r)
				{
					int mid=(l+r)/2;
					if(a[now].r<=b[mid].r)
						r=mid-1,ans2=mid;
					else
						l=mid+1;
				}
				if(find1(ans1)!=find1(ans2))
					f1[f1[ans1]]=f1[ans2],--ans,ans3+=bq,f[find(a[now].l)]=find(a[now].r);
		 	} 
		}
		for(int i=1;i<=top;++i)
			ans3+=b[i].z;
		cout<<ans3<<'\n';
		ans3=0;
	}
	return 0;
 } 
